\section{Algoritmo de Touch Count}
\subsection{Motivación:Problemas de LRU}

El algoritmo LRU (Least Recently Used) es una estrategia bien conocida para reemplazo de buffers en una caché. Al hacérsele una lectura de una página que no está en el caché, y habiéndose quedado sin espacio, LRU elige la página cuya última lectura es la más vieja (de aquí su nombre). 

Una implementación sencilla de ésto consiste en utilizar una lista. En uno de sus extremos, que denominaremos extremo LRU, vamos posicionando a las páginas recientemente accedidas ; al otro extremo, que llamaremos extremo MRU, se irán moviendo las páginas cuando no sean utilizadas. La idea intuitiva detrás del algoritmo LRU es que las páginas que no son populares irán migrando al extremo MRU, y cuando lleguen a éste serán reemplazadas. Por otro lado, las páginas populares deberían mantenerse en el extremo LRU. 

Esta estrategia, cuyo funcionamiento es muy bueno para cachés en procesadores, sufre de algunos problemas ante ciertos patrones de acceso a disco. El caso más emblemático es el del File Scan. Esta operación, ejecutada sobre una tabla, limpia todo el caché de los elementos que tenía anteriormente, muy a pesar de que probablemente no utilizaremos nuevamente los bloques de la tabla recorrida. Ésto es inaceptable para la performance de un DBMS.

Hay variaciones del algoritmo LRU que permiten atacar el problema del File Scan, pero sucumben de igual manera frente a otras operaciones (como un gran Index Scan). Por otro lado, el algoritmo MRU (Most Recently Used) no tiene problema con File/Index Scans (sólo reemplaza un bloque para ellos), pero no es una alternativa viable ya que contradice el principio básico de una caché: el Principio de Vecindad Temporal, que reza que un elemento recientemente accedido será accedido nuevamente con alta probabilidad.

\subsection{Introducción a Touch Count}

El algoritmo de Touch Count intenta captar esa intuición que teníamos sobre el algoritmo LRU: "las páginas populares se mantendrán en el extremo MRU, y las impopulares migrarán hacia el extremo LRU". La idea principal es que cada bloque se gane no sólo el derecho a entrar a la caché, sino también a permanecer en ésta.

La popularidad de un bloque en la caché es medida mediante un contador asignado que llamaremos "count". Cada vez que un bloque es accedido, se incrementa el valor de este contador. A su vez, a medida que este contador no se incremente, será decrementado y debido a ésto irá migrando hacia el extremo LRU de la lista.

\subsection{Descripción de Touch Count}

\subsubsection{Extremos hot y cold}

La lista LRU la dividiremos en dos secciones: la sección "hot" (elementos populares) y la sección "cold" (elementos no tan populares). ¿Cuántos elementos tendremos en cada lado? Por defecto, se tiene un 50\% de los buffers totales de cada lado, pero este parámetro es configurable.

Cuando se lee de disco un bloque, éste es colocado en la "mitad" entre las listas hot y cold. A esto lo llamaremos inserción por la mitad (midpoint insertion). Esta decisión hace que los bloques recién accedidos no se conviertan automáticamente en populares, sino que deban ganárselo.

En las siguientes secciones veremos cómo se determina la estancia en cada una de estas secciones. 

\subsubsection{Incremento del Touch Count}

Teóricamente, cada vez que un buffer en la caché es accedido (sea por lectura o escritura) se incrementa su touch count. En la práctica ésto no es así ya que suelen existir breves ráfagas de acceso a ciertos bloques, y que luego caiga su uso en desgracia. Para evitar éso, se puede establecer una ventana de tiempo en la cual sólo se pueda incrementar una vez el buffer. La implementación de Oracle utiliza una ventana de 3 segundos.

\subsubsection{Movimiento de los buffers}

Cuando un bloque es traído a la caché es colocado en el medio de la lista, entre las secciones hot y cold. A diferencia de los algoritmos LRU/MRU, un buffer no es movido en la lista sólo porque ha sido accedido; tan sólo se incrementará eventualmente su touch count.

El movimiento de buffers se realiza cuando se busca un sitio donde poner un bloque que no está en la caché. Un buffer "libre" se le llamará o bien al que no aloja ninguna página o bien no está "dirty" (es decir, su contenido es el mismo en memoria y disco). 

Cuando el DBMS busca un buffer libre (una víctima), lo que éste hace es reordenar la lista, para luego elegir el buffer "más frío". Lo que hace para reordenar la lista es descripto a continuación.

En primer lugar, si encontramos un buffer cualquiera (hot o cold) cuyo touch count es mayor a dos, se mueve al extremo MRU (hot) de la lista. Además, luego de ser movido al extremo hot, se le setea su count a 0. Ambos parámetros (el threshold para ser promovido a hot, y cómo se le setea el count luego de ésto) son configurables.

Luego de este reordenamiento, es probable que la proporción de elementos hot y cold esté desbalanceada. Entonces, habrá que bajar elementos de hot a cold. Cuando un buffer desciende a cold, su count se resetea a 1.




